package leetcode;

import java.util.*;
import java.util.Map.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-24 00:14
 **/
public class LeetCode347 {

    /**
     * 使用了Map+优先队列解决该题
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent(int[] nums, int k) {
        //使用Map统计每个元素出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        int size = nums.length;
        int i = 0;
        for (; i < size; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        //使用优先队列队列(大根堆)
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        Set<Map.Entry<Integer, Integer>> set = map.entrySet();
        for (Map.Entry<Integer, Integer> entry : set) {
            queue.offer(new int[]{entry.getKey(), entry.getValue()});
        }
        //定义结果数组
        int[] result = new int[k];
        //定义结果数组当前索引
        int index = 0;
        while (!queue.isEmpty() &&  index < k) {
            result[index++] = queue.poll()[0];
        }
        return result;
    }

}
